|
Computability theory, also called recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The basic questions addressed by recursion theory are "What does it mean for a function on the natural numbers to be computable?" and "How can noncomputable functions be classified into a hierarchy based on their level of noncomputability?". The answers to these questions have led to a rich theory that is still being actively researched. The field has since grown to include the study of generalized computability and definability. Invention of the central combinatorial object of recursion theory, namely the Universal Turing Machine, predates and predetermines the invention of modern computers. Historically, the study of algorithmically undecidable sets and functions was motivated by various problems in mathematics that turned to be undecidable; for example, word problem for groups and the like. There are several applications of the theory to other branches of mathematics that do not necessarily concentrate on undecidability. The early applications include the celebrated Higman's embedding theorem that provides a link between recursion theory and group theory, results of Michael O. Rabin and Anatoly Maltsev on algorithmic presentations of algebras, and the negative solution to Hilbert's Tenth Problem. The more recent applications include algorithmic randomness, results of Soare et al. who applied recursion-theoretic methods to solve a problem in algebraic geometry,〔Csima, Barbara F., et al. "Bounding prime models." The Journal of Symbolic Logic 69.04 (2004): 1117-1142.〕 and the very recent work of Slaman et al. on normal numbers that solves a problem in analytic number theory. Recursion theory overlaps with proof theory, effective descriptive set theory, model theory, and abstract algebra. Arguably, computational complexity theory is a child of recursion theory; both theories share the same technical tool, namely the Turing Machine. Recursion theorists in mathematical logic often study the theory of relative computability, reducibility notions and degree structures described in this article. This contrasts with the theory of subrecursive hierarchies, formal methods and formal languages that is common in the study of computability theory in computer science. There is a considerable overlap in knowledge and methods between these two research communities; however, no firm line can be drawn between them. For instance, parametrized complexity was invented by a complexity theorist Michael Fellows and a recursion theorist Rod Downey. ==Computable and uncomputable sets== Recursion theory originated in the 1930s, with work of Kurt Gödel, Alonzo Church, Alan Turing, Stephen Kleene and Emil Post.〔Many of these foundational papers are collected in ''The Undecidable'' (1965) edited by Martin Davis.〕 The fundamental results the researchers obtained established Turing computability as the correct formalization of the informal idea of effective calculation. These results led Stephen Kleene (1952) to coin the two names "Church's thesis" (Kleene 1952:300) and "Turing's Thesis" (Kleene 1952:376). Nowadays these are often considered as a single hypothesis, the Church–Turing thesis, which states that any function that is computable by an algorithm is a computable function. Although initially skeptical, by 1946 Gödel argued in favor of this thesis: :"Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an interesting epistemological notion, i.e., one not depending on the formalism chosen. *"(Gödel 1946 in Davis 1965:84).〔The full paper can also be found at pages 150ff (with commentary by Charles Parsons at 144ff) in Feferman et al. editors 1990 ''Kurt Gödel Volume II Publications 1938-1974'', Oxford University Press, New York, ISBN 978-0-19-514721-6. Both reprintings have the following footnote * added to the Davis volume by Gödel in 1965: "To be more precise: a function of integers is computable in any formal system containing arithmetic if and only if it is computable in arithmetic, where a function ''f'' is called computable in ''S'' if there is in ''S'' a computable term representing ''f'' (p. 150).〕 With a definition of effective calculation came the first proofs that there are problems in mathematics that cannot be effectively decided. Church (1936a, 1936b) and Turing (1936), inspired by techniques used by Gödel (1931) to prove his incompleteness theorems, independently demonstrated that the Entscheidungsproblem is not effectively decidable. This result showed that there is no algorithmic procedure that can correctly decide whether arbitrary mathematical propositions are true or false. Many problems in mathematics have been shown to be undecidable after these initial examples were established. In 1947, Markov and Post published independent papers showing that the word problem for semigroups cannot be effectively decided. Extending this result, Pyotr Novikov and William Boone showed independently in the 1950s that the word problem for groups is not effectively solvable: there is no effective procedure that, given a word in a finitely presented group, will decide whether the element represented by the word is the identity element of the group. In 1970, Yuri Matiyasevich proved (using results of Julia Robinson) Matiyasevich's theorem, which implies that Hilbert's tenth problem has no effective solution; this problem asked whether there is an effective procedure to decide whether a Diophantine equation over the integers has a solution in the integers. The list of undecidable problems gives additional examples of problems with no computable solution. The study of which mathematical constructions can be effectively performed is sometimes called recursive mathematics; the ''Handbook of Recursive Mathematics'' (Ershov ''et al.'' 1998) covers many of the known results in this field. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Computability theory」の詳細全文を読む スポンサード リンク
|